#include<iostream>
#include<cstring>
using namespace std;
struct AVLnode {
int key; //关键词
int height; //以该结点为根的子树高度
AVLnode *left, *right;
AVLnode(int K){ key=K; height=0; left=right=NULL; }
};
int flag;
int Height(AVLnode *t){ return(t==NULL)?-1:t->height; }
void UpdateHeight(AVLnode *t){
t->height = max(Height(t->left),Height(t->right))+1;
}
bool find(int k,AVLnode * root){
    if(root->key==k)return 1;
    if(root->key<k&&root->right)return find(k,root->right);
    if(root->key>k&&root->left)return find(k,root->left);
    return 0;
}
void LL(AVLnode * &A){
    AVLnode *B=A->left;
    A->left=B->right;
    B->right=A;
    UpdateHeight(A);
    UpdateHeight(B);
    A=B;
}
void RR(AVLnode * &A){
    AVLnode *B=A->right;
    A->right=B->left;
    B->left=A;
    UpdateHeight(A);
    UpdateHeight(B);
    A=B;
}
void LR(AVLnode * &A){
    RR(A->left);
    LL(A);
}
void RL(AVLnode * &A){
    LL(A->right);
    RR(A);
}
void Balence(AVLnode * &root,int k,int dep,int op,int &bj){
    if(root==NULL)return;
    if(Height(root->left)-Height(root->right)==2){
        if(Height(root->left->left)>=Height(root->left->right)){
            flag=1;
            LL(root);
            if(!bj){
            if(op==1)printf("Insert %d: ",k);
            if(op==2)printf("Remove %d: ",k);
            bj=1;
            }
            printf("Rebalance subtree rooted at node %d on level %d with right rotation. ",root->right->key,dep);
        }
        else{
            LR(root);
              if(!bj){
            if(op==1)printf("Insert %d: ",k);
            if(op==2)printf("Remove %d: ",k);
            bj=1;
            }
            printf("Rebalance subtree rooted at node %d on level %d with left rotation and right rotation. ",root->right->key,dep);
        }
         
    }else if(Height(root->right)-Height(root->left)==2){
        flag=1;
        if(Height(root->right->right)>=Height(root->right->left)){
            RR(root);
              if(!bj){
                if(op==1)printf("Insert %d: ",k);
            if(op==2)printf("Remove %d: ",k);
            bj=1;
            }
            printf("Rebalance subtree rooted at node %d on level %d with left rotation. ",root->left->key,dep);
        }
        else{
            RL(root);
            if(!bj){
            if(op==1)printf("Insert %d: ",k);
            if(op==2)printf("Remove %d: ",k);
            bj=1;
            }
            printf("Rebalance subtree rooted at node %d on level %d with right rotation and left rotation. ",root->left->key,dep);
        }
    }
    UpdateHeight(root);
}
void Insert(AVLnode * &root,int k,int dep,int & bj){
    if(root==NULL)root=new AVLnode(k);
    else if(k<root->key){
        Insert(root->left,k,dep+1,bj);
    }
    else if(k>root->key){
        Insert(root->right,k,dep+1,bj);
    }
    Balence(root,k,dep,1,bj);
}
void remove(AVLnode * &root,int k,int dep,int yk,int & bj){
    if(root==NULL)return;
    if(k<root->key)remove(root->left,k,dep+1,yk,bj);
    else if(k>root->key)remove(root->right,k,dep+1,yk,bj);
    else if(root->left!=NULL&&root->right!=NULL){
        AVLnode *s=root->right;
        while(s->left!=NULL)s=s->left;
        root->key=s->key;
        remove(root->right,s->key,dep+1,yk,bj);
    }
    else{
        AVLnode * oldroot=root;
        root=(root->left!=NULL)?root->left:root->right;
        delete oldroot;
    }
    Balence(root,yk,dep,2,bj);
}
void zx(AVLnode *root){
    if(root->left)zx(root->left);
     printf("%d ",root->key);
    if(root->right)zx(root->right);
}
void qx(AVLnode *root){
     printf("%d ",root->key);
    if(root->left)qx(root->left);
    if(root->right)qx(root->right);
}
int bj[2000000];
int main(){
    int n;
    int cnt=1;
   while(cin>>n){
    if(cnt!=1)printf("\n");
    flag=0;
    printf("Case %d:\n",cnt);
    int x;
    cnt++;
  char op[10];
    cin>>op;
    scanf("%d",&x);
    AVLnode * root=new AVLnode(x);
    for(int i=1;i<n;i++){
        
      cin>>op;
        scanf("%d",&x);
        if(op[0]=='I'){
            if(find(x,root)==0){
                int bj=0;
                Insert(root,x,0,bj);
                if(bj)printf("\n");
            }
        }
        if(op[0]=='R'){
            if(find(x,root)){
                int bj=0;
                remove(root,x,0,x,bj);
                if(bj)printf("\n");
            }
        }
    }
    if(flag)printf("\n");
    zx(root);
    printf("\n\n");
    qx(root);
    printf("\n");
   }
    return 0;
}